Given a finite set U, finding a minimal subset X* of the finite set U satisfying a given property P is a frequent problem in computer science. For instance, this problem can be found in diagnosis (e.g., find a minimal subset of faulty components of a system that explains the current observations) or in non-monotonic logics (e.g., find a minimal subset of abnormalities in the clauses that restore admissibility).
In several important applications the property P is upward-closed, that is, whenever it holds for a subset X it also holds for any superset of X. This is typically the case in the identification of minimal infeasible subsets (conflicts) of constraints C in optimization models. If a subset X of constraints is infeasible then any superset of X clearly is infeasible too. This is described in more detail in John W. Chinneck, “Finding a useful subset of constraints for analysis in an infeasible linear program”, INFORMS Journal on Computing, 9:164-174, 1997.
In a first simple example, a constraint is an object that describes a relation between several objects that must be enforced. For instance: “the salary of a person must be above $10 per hour”. A constraint is said to be satisfied for a given instance if it is true for the case considered: “Peter's salary is $15 per hour”—where Peter is the instance considered. In other cases, a constraint may be unsatisfied for a given instance: “John's salary is $8 per hour”.
Complex optimization problems are assemblies of thousands or hundreds of thousands of such constraints, most often much more complex ones, coupled to instances that are to meet the constraints.
For instance, consider the very simple set of statements (constraints and instances) assuming there are 3 persons in a company (John, Peter and Mary):                A—the total budget per hour has to be between $25 and $30        B—the salary of a manager must be strictly above that of his or her employees and John is Peter's manager        C—John's salary is $10        D—Mary's salary is $20        E—the salary of a person must be at or above $10 per hour        
These statements boil down to the following constraints:                A1: 25≦salary[John]+salary[Peter]+salary[Mary]        A2: salary[John]+salary[Peter]+salary[Mary]≦30        B1: salary[John]>salary[Peter]        C1: salary[John]=10        D1: salary[Mary]=20        E1: salary[John]≧10        E2: salary[Peter]≧10        E3: salary[Mary]≧10        
The question asked is “find a salary for John, Peter and Mary that meets all the above constraints”. It is desirable to rapidly answer such kinds of questions which in practice are much more complex with many more variables. In the above example, the problem cannot be solved and therefore the set of constraints is infeasible. Two possible example explanations for infeasibility of the problem are:                1. The total budget for the 3 employees cannot exceed $30 (A2), but the salary of John is $10 (C1), the one of Mary $20 (D1) and the one of Peter at least $10 (E2) thus the total budget will be at least $40; and        2. John's salary cannot be more than $10 (C1). As Peter's salary is at least $10 (E2), this is not consistent with constraint B1 stating that because John is Peter's manager his salary should be above that of Peter's salary.        
Both explanations 1 and 2 above are minimal in the sense that removing any constraint from the explanation leads to a feasible sub-problem. For instance explanation 2 consists of constraints (B1, C1, E2). If one removes constraint B1, the system (C1, E2) is feasible (for instance with salary[John]=10, salary[Peter]=10). If one removes constraint C1, the system (B1, E2) is feasible (for instance with salary[John]=15, salary[Peter]=10). If one removes constraint E2, the system (B1, C1) is feasible (for instance with salary[John]=10, salary[Peter]=9).
FIG. 1 shows a finite set U of 16 constraints Ci. Constraints Ci can be, for example x<y. It is desired to compute a minimal explanation of constraints to show infeasibility of an optimization model. In the example of FIG. 1, constraint C2 of x<y, constraint C8 of y<z and constraint C12 of z<x forms a minimal explanation 102 since all three constraints cannot be satisfied. Other minimal explanations are constraints C4, C5 and C14 (104) and constraints C4, C9 and C16 (106).
Typically, methods of finding a minimal subset work by iteratively checking some subsets of constraints for infeasibility. FIG. 2 shows the subsets which may be checked by a typical method. In a first check a subset 202 comprising C1, C3, C4, C5, C7, C9, C10, C14 and C16 is checked. This subset is found to be infeasible. However, further checks are done to see if this is a minimal infeasible subset. In a second check, constraints C9 and C16 are deleted from the subset, and a subset 204 comprising C1, C3, C4, C5, C7, C10 and C14 is checked. This subset is also found to be infeasible. In a third check, constraint C4 is deleted from the subset, and a subset 206 comprising C1, C3, C5, C7, C10 and C14 is checked. This subset is found to be feasible and so is not a minimal infeasible subset. In a fourth check, constraint C4 is replaced in the subset, constraints C1, C3, C5, C10 are deleted from the subset, and a subset 208 comprising C4, C7 and C14 is checked. This subset is found to be feasible and so is also not a minimal infeasible subset. In a fifth check, constraint C5 is replaced in the subset, constraint C7 is deleted from the subset, and a subset 210 comprising C4, C5, and C14 is checked. This subset is found to be infeasible and is a minimal subset. The performance of a method of finding a minimal subset is estimated by counting the number of checks before finding a minimal explanation.
In general, checking property P for a particular subset X is an expensive operation. It may be NP-complete. The abbreviation NP stands for “nondeterministic polynomial time”. This means that the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows.
Frequently, approaches for solving this minimal subset problem rely on the particular features of the property P being considered. For instance in the optimization context mentioned above, John W. Chinneck, “Finding a useful subset of constraints for analysis in an infeasible linear program”, INFORMS Journal on Computing, 9:164-174, 1997 discloses the use of elastic filters for Linear Programming models. Narendra Jussien and Olivier Lhomme, “Local search with constraint propagation and conflict-based heuristics”, Artificial Intelligence, 139(1):21-45, July 2002 discloses explanations recording for Constraint Programming models. Joao P. Marques Silva and Karem A. Sakallah, “Conflict analysis in search algorithms for satisfiability”, in Proceedings of the 8th International Conference on Tools with Artificial Intelligence (ICTAI'96), 1996, discloses no-goods learning for Boolean Satisfiability models.
But the logic behind checking property P for a particular subset X can be so complex that it may turn out to be necessary or advantageous to consider it as a black box operation. Property P(X) could for instance be the outcome of a complex simulation process based on a set of input events X. In the context of minimal conflicts identification, the advances in the optimization state-of-the-art result in increasingly sophisticated and efficient engines. Such engine's sophistication makes it harder to implement intrusive methods to compute minimal conflicts whereas increase of the engine's efficiency makes infeasibility property checking faster. Both aspects tend to make the black box approach more attractive.
It is desirable to find a minimal subset satisfying an upward-closed property without any knowledge of the property except for the assumption that it is upward-closed. The complexity measure typically considered is therefore the number of property checks performed. So far, two types of approaches have been used to solve this problem, recursive approaches and iterative approaches.
Ulrich Junker, “QuickXplain: Preferred explanations and relaxations for over-constrained problems”, in Proc. AAAI-04, 2004 discloses a recursive approach implemented in the QuickXplain algorithm.
Fred Hemery, Christophe Lecoutre, Lakhdar Sais, and Frederic Boussemart, “Extracting MUCs from constraint networks”, In Proc. 17th European Conference on Artificial Intelligence (ECAI'06), 2006 discloses an iterative approach called the dichotomic algorithm (DC).
The iterative method of an exemplary embodiment of the present invention is shown to outperform the above approaches in both extremal cases when the selected minimal subset is small and when it is large. An experimental study on randomly generated instances suggests that this method also outperforms existing methods in between those extremal cases.
U.S. Pat. No. 7,478,297 B2 discloses finding diagnosis for integrated logic circuit. U.S. Pat. No. 7,337,090 B1 is also about diagnosis but in a more general context than U.S. Pat. No. 7,478,297 B2. A part of the process depicted on the right part of FIG. 3A (blocks 317-318-313-320) could be considered as the problem of finding as a minimal subset satisfying an upward bounded property (just like the problem of finding a minimal infeasible subset). Indeed if S is a valid subset of symptoms (i.e., an infeasible subset), then any superset of this subset is also valid. The patent discloses checking all symptoms individually (block 317), which corresponds to a “naive” method.
U.S. Pat. No. 6,336,110 B1 discloses finding a solution to a constraint satisfaction problem.
I. Shah, “A Hybrid Algorithm for Finding Minimal Unsatisfiable Subsets in Over-constrained CSPs” International Journal of Intelligent Systems, Volume 26, Issue 11, November 2011, Pages 1023-1048 and Mark H Liffiton and Karem A Sakallah, “Algorithms for Computing Minimal Unsatisfiable Subsets of Constraints”, Journal of Automated Reasoning, 40(1):1-33, January 2008 aims at computing several (and even all) Minimal Unsatisfiable Subsets (MUSes). In order to do so, the approaches strongly rely on the duality between Minimal Unsatisfiable Subsets and Minimal Correction Sets. It would be desirable to focus on the problem of computing ONE unsatisfiable subset. In the context of computing ONE unsatisfiable subset, the approaches presented in the above papers are not efficient because they initially require the computation of several or all Minimal Correction Sets, which is far too expensive if one is only interested in ONE unsatisfiable subset.
It would be desirable to have a method to find a minimal explanation for infeasibility of an optimization model that improves on the performance of existing methods and is shown to be optimal on both extreme cases (i.e., small explanations/large explanations).